
// 设计算法，利用顺序栈和循环队列的基本运算，判断字符串是否是回文。

#include "stdio.h"
#include <stdlib.h>
#define CycleMaxSize 20
typedef char ElementType;

// 队列数据结构定义
typedef struct CycleQueue
{
    // 存放数据的数组
    ElementType datas[CycleMaxSize];
    // 队列头所在的数组下标
    int front;
    // 队列尾所在的数组下标
    int rear;
} CycleQueue;

// 初始化一个循环队列
/*
 * 思路:
 * 分配存储空间
 * 队头和队尾置 0
 * 返回队列指针
 */
CycleQueue *InitCycleQueue()
{
    CycleQueue *queue = (CycleQueue *)malloc(sizeof(CycleQueue));
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

// 循环队列入队
/*
 * 思路:
 * 判断队列是否已经满
 * 没有满的话将元素插入到队尾
 * 队尾下标 +1
 */
int PushElementQueue(CycleQueue *queue, ElementType data)
{
    if ((queue->rear + 1) % CycleMaxSize == queue->front)
    {
        // 队列满
        printf("队列已经满了\n");
        return 0;
    }
    queue->datas[queue->rear] = data;
    queue->rear = (queue->rear + 1) % CycleMaxSize;
    return 1;
}

// 出队
/*
 * 思路:
 * 判断队列是否已经空
 * 没有空的话将队头元素返回
 * 队首下标 +1
 */
ElementType PopElementQueue(CycleQueue *queue)
{
    if (queue->front == queue->rear)
    {
        printf("队列为空,无法出队\n");
        return 0;
    }
    ElementType value = queue->datas[queue->front];
    // 出队之后更新队头下标的位置
    queue->front = (queue->front + 1) % CycleMaxSize;
    return value;
}

// 打印循环队列
void PrintCycleQueue(CycleQueue *queue)
{
    int count = queue->rear - queue->front;
    int i = queue->front;
    for (i; i < queue->rear; i++)
    {
        printf("%c->", queue->datas[i]);
    }
}

// 定义一个循环栈
typedef struct CycleStack
{
    ElementType datas[CycleMaxSize];
    int front;
} CycleStack;

// 初始化一个顺序栈
CycleStack *InitCycleStack()
{
    CycleStack *stack = (CycleStack *)malloc(sizeof(CycleStack));
    stack->front = 0;
    return stack;
}

// 顺序栈入栈
int PushElementStack(CycleStack *stack, ElementType data)
{
    if (stack->front == CycleMaxSize)
    {
        printf("队列已经满了,无法插入%d\n", data);
        return 0;
    }
    stack->datas[stack->front] = data;
    // 入队之后更新栈顶元素下标的值
    // printf("这时候栈顶元素下标是%d,栈顶元素值是%d\n",stack->front,stack->datas[stack->front]);
    stack->front++;
    return 1;
}

// 顺序栈出栈
ElementType PopElementStack(CycleStack *stack)
{
    if (stack->front == 0)
    {
        printf("顺序栈为空,不能出栈\n");
        return 0;
    }
    ElementType value = stack->datas[stack->front - 1];
    // 出队之后更新栈顶元素的值
    stack->front--;
    return value;
}

// 打印顺序栈
void PrintCycleStack(CycleStack *stack)
{
    printf("\n");
    int i;
    for (i = 0; i < stack->front; i++)
    {
        printf("%c->>", stack->datas[i]);
    }
}

int main(int argc, char *argv[])
{
    CycleQueue *queue = InitCycleQueue();
    CycleStack *stack = InitCycleStack();

    /**
     * 判断回文数思路,同时入队入栈,最后同时出队出栈,若出来的元素一致则是回文字符串。
     * 无非就是利用特性判断逆序,其实可以直接逆转然后判断
     */
    int flag = 1;
    char inputStr;
    char popEleByStack, popEleByQueue;
    printf("依次输入字符,以回车键结束:\n");
    inputStr = getchar();
    while (inputStr != '\n')
    {
        PushElementStack(stack, inputStr);
        PushElementQueue(queue, inputStr);
        inputStr = getchar();
    }
    PrintCycleQueue(queue);
    PrintCycleStack(stack);
    printf("\n");
    printf("栈和队列中的元素总数是%d\n",stack->front);
    int i;
    int count = stack->front;
    for (i = 0; i < count; i++)
    {
        popEleByQueue = PopElementQueue(queue);
        printf("出队的值是%c\n", popEleByQueue);
        popEleByStack = PopElementStack(stack);
        printf("出栈的值是%c\n", popEleByStack);
        if (popEleByQueue != popEleByStack)
        {
            printf("进去了判断\n");
            flag = 0;
            break;
        }
        
    }
    if (flag ==1)
    {
        printf("是回文字符串");
    }else{
        printf("不是回文字符串");
    }

    return 0;
}